home *** CD-ROM | disk | FTP | other *** search
/ CD Ware Multimedia 1995 May / cd Ware (Juegos) Epimundo.iso / DOS / C / LLIST.ZIP / LISTLIST.DOC < prev    next >
Encoding:
Text File  |  1993-11-26  |  19.1 KB  |  526 lines
  1.  
  2.  
  3.  
  4.                L I S T L I S T   5.0   U S E R ' S   G U I D E
  5.               =================================================
  6.  
  7. SUMMARY:...................................................................... 
  8.  
  9. ListList is an easy-to-use linked list manager.  It solves the general 
  10. problem of how to organize odd pieces of data held anywhere in memory.  
  11. Comes complete with a user's guide, source code for a library of over 100 
  12. carefully explained procedures and a comprehensive test program.  
  13. Features a fast method for sorting long lists. Written in portable ANSI 'C'.  
  14. Distributed on a try-before-you-buy basis; price $5.
  15.  
  16.  
  17. INTRODUCTION:.................................................................
  18.  
  19. All computer programs manipulate data. The form in which data is held has an 
  20. impact on the procedures that use that data.  If the data is well organized 
  21. and easily accessible then the procedures can be written in a clear and 
  22. easily understood way.  In other words, clean data structures permit clean 
  23. procedures.
  24.  
  25. Data can be of irregular size and there may be lots of it.  In general, how 
  26. does one grasp and deal with many different things?  A natural way to organize 
  27. many things is to make a list.  
  28.  
  29. Lists inside a computer can be represented as a flexible data structure called 
  30. a linked list.  A linked list can make processing data easier by ordering and 
  31. grouping related data.
  32.  
  33. A SIMPLE EXAMPLE USING LISTLIST:..............................................
  34.  
  35. As a demonstration let's make a list of names, sort the list and then search 
  36. for a particular name in the list.  The details will be explained later.
  37.  
  38.  
  39. Here's a picture of the list we will make:
  40.  
  41.  
  42.          'AList' ----> [LIST]
  43.                          |
  44.                        [ITEM]--->[Dagny Taggart]
  45.                          |
  46.                        [ITEM]--->[Francisco d'Anconia]
  47.                          |
  48.                        [ITEM]--->[Hank Reardon]
  49.                          |
  50.                        [ITEM]--->[Hugh Akston]
  51.                          |
  52.                        [ITEM]--->[John Galt]
  53.  
  54. Building the list:
  55.  
  56.  
  57.     AddressOfList    AList;  /* This variable holds the     */
  58.                              /* address of the list record. */
  59.  
  60.      /* These are the data records to be itemized. */
  61.      Byte    John[]   = "John Galt";
  62.      Byte    Dagny[]  = "Dagny Taggart";
  63.      Byte    Hank[]   = "Hank Reardon";
  64.      Byte    Frisco[] = "Francisco d'Anconia";
  65.      Byte    Hugh[]   = "Hugh Akston";
  66.  
  67.      AList = CreateList();  /* Allocate a new list record */
  68.  
  69.     InsertDataLastInList( AList, Dagny  );
  70.     InsertDataLastInList( AList, Frisco );
  71.     InsertDataLastInList( AList, Hank   );
  72.     InsertDataLastInList( AList, Hugh   );
  73.     InsertDataLastInList( AList, John   );
  74.  
  75. Sorting the list:
  76.  
  77.     SortListAlphabetically( AList );
  78.  
  79. Searching the list: 
  80.  
  81.     SearchKey      = (AddressOfByte) "John";
  82.     KeyFieldOffset = 0;
  83.     KeyFieldWidth  = 4;
  84.  
  85.     MatchingItem = FindFirstMatchingItem( AList, 
  86.                                           KeyFieldOffset, 
  87.                                           KeyFieldWidth, 
  88.                                           SearchKey );
  89.  
  90.  
  91. End of Example.
  92.  
  93. WHAT ELSE CAN BE DONE WITH LISTLIST:..........................................
  94.  
  95. Usage is not limited to lists of strings: any kind of data located anywhere in 
  96. addressable memory can be itemized and manipulated via lists.  ListList can be 
  97. used to make structures like stacks, queues, symbol tables, hierarchies and 
  98. databases.
  99.  
  100. A list can be used as a stack:
  101.  
  102.                    [ ] <--> [ ]=[ ]=[ ]=[ ]
  103.  
  104. A list can be used as a queue:
  105.  
  106.                    [ ] <-- [ ]=[ ]=[ ] <-- [ ]
  107.  
  108. A list can refer to other lists:
  109.  
  110.                    [ ]->[ ]=[ ]=[ ] 
  111.                     |
  112.                    [ ]->[ ]  
  113.                     |
  114.                    [ ]->[ ]=[ ] 
  115.  
  116. LEARNING TO USE LISTLIST:.....................................................
  117.  
  118. Read through the Theory of Operation section below then see the source code 
  119. and test program for examples.
  120.  
  121. Every procedure in the source code is preceded by a comment block.  The 
  122. comment block headings are self explanitory except for 'ASSUMES'.  These are 
  123. the assumptions that must be true in order for the procedure to work properly.  
  124. If a condition is listed under the 'ASSUMES' heading then no test is made 
  125. within the procedure to determine if the condition exists: it is assumed to 
  126. hold.
  127.  
  128. The source code itself is written in a descriptive way.  I strive to write 
  129. code that MUST work, not just code that happens to work.   To do this it has 
  130. to be written simply and clearly so that it can be validated conceptually 
  131. prior to running it.  And then I test it. 
  132.  
  133. I rank clarity over brevity of code.  My theory of software writing and 
  134. validation is best expressed by this quote from Oliver Heaviside, the self-
  135. taught 19th Century physicist:
  136.  
  137.                "The best of all proofs is to set out the fact 
  138.               descriptively so that it can be seen to be a fact." 
  139.  
  140.  
  141. THEORY OF OPERATION:..........................................................
  142.  
  143. This section is broken into five parts:
  144.  
  145.     1. The Item Record: Building Block Of Linked Lists
  146.     2. The List Record: Place Holder For A List
  147.     3. Operations: How To Operate On A Linked List
  148.     4. The List Stack: A Convenient Place To Preserve List Addresses
  149.     5. SetUp & CleanUp: What To Do First & Last
  150.  
  151. THE ITEM RECORD: BUILDING BLOCK OF LINKED LISTS...............................
  152.  
  153. The basic idea behind the linked list is that each element of data is 
  154. represented by a uniform data record called an item. 
  155.  
  156. Items can be connected together into chains so that related data can be 
  157. grouped together and accessed in a desired order.
  158.  
  159. Item records provide a basic ordering and directory function.  From an item 
  160. record it is possible to find the location of the data associated with that 
  161. item, and the locations of the items before and after the item.
  162.  
  163. Each item record consists of four elements:
  164.  
  165.     1. The address of the data that the item stands for. 
  166.     2. The address of the prior item in the list.
  167.     3. The address of the next item in the list.
  168.     4. A mark used to select or distinguish an item from other  items in the     
  169.        same list.
  170.  
  171.              [ITEM] (2)
  172.                ^
  173.                |           Item Record
  174.                |   --------------------------
  175.                ----|   AddressOfPriorItem   |
  176.                    |------------------------|
  177.                ----|   AddressOfNextItem    |
  178.                |   |------------------------|      (1)
  179.                |   |     AddressOfData      |--->[ DATA....//.... ]    
  180.                |   |------------------------|
  181.                |   |       ItemMark         |
  182.                |   --------------------------
  183.                |             (4)
  184.              [ITEM] (3)
  185.  
  186.  
  187. The 'ItemMark' field of an item record is used to signify that an item is 
  188. special in some way.  Some situations call for the selection of some items of 
  189. data from a wider group based on a selection criteria.  For example, in a list 
  190. of names it may be desirable to delete all data records containing the last 
  191. name 'Smith'.  A procedure might be written to scan through the list and mark 
  192. all items that refer to data containing  the name 'Smith'.  Then the routine 
  193. 'DeleteMarkedItems()' could be called to complete the job.
  194.  
  195. THE LIST RECORD: PLACE HOLDER FOR A LIST......................................
  196.  
  197. Items of a list can be inserted, extracted and reordered.  But what happens 
  198. when the last item of a list is extracted?  Does the list go away?
  199.  
  200. The need for a fixed way of referring to a list, apart from the items it 
  201. contains, gives rise to the need for a second kind of record, the List Record:
  202.                           
  203.                          List Record
  204.                  --------------------------
  205.                  |   AddressOfFirstItem   |--->[ITEM]--[ITEM]--[ITEM]
  206.                  |------------------------|                       ^
  207.                  |   AddressOfLastItem    |-----------------------|
  208.                  |------------------------|       
  209.                  |       ItemCount        |    
  210.                  |------------------------|
  211.                  |       ListMark         |
  212.                  --------------------------
  213.  
  214. A list record is a place holder for the list and contains information about 
  215. the list: how many items there are, where the first and last item records can
  216. be found and a 'ListMark' field similar in function to the 'ItemMark' field 
  217. in the item record.
  218.  
  219. The 'AddressOfLastItem' field is included solely for speed: when items are 
  220. appended to the end of a list, the last item can be located directly without 
  221. having to travel through the entire list.  Also, the performance of operations 
  222. that scan a list in reverse order is improved by the ability to go directly to 
  223. the last item.
  224.  
  225. The 'ItemCount' field holds a count of the items in the list and is kept 
  226. current by all of the procedures that insert or extract items.  The 
  227. 'ItemCount' field saves time by eliminating the need to count the items in 
  228. a list.
  229.  
  230. The 'ListMark' field is used to signal that the list as a whole is special in 
  231. some way.  Lists can be marked and later that mark can be used to control 
  232. processing of the list in the same way the 'ItemMark' field allows delayed 
  233. processing of marked items.
  234.  
  235. OPERATIONS: HOW TO OPERATE ON A LINKED LIST...................................
  236.  
  237. ListList contains two major classes of operations:
  238.  
  239.     1. General list functions which operate on any given list.
  240.  
  241.     2. Special list functions which operate only on the current list.
  242.  
  243. A general list function is any procedure that requires the address of a 
  244. list as a parameter.  For example,
  245.  
  246.     DeleteList(AddressOfList);
  247.     DuplicateList(AddressOfList);
  248.     ExtractItemFromList(AddressOfList,AddressOfItem);
  249.  
  250. A special list function is a procedure that operates on the list currently 
  251. referenced by the global variable 'TheList'.  Here are some examples of this 
  252. kind of list operation:
  253.  
  254.     ToFirstItem();
  255.     ToLastItem();
  256.     ToNextItem();
  257.     ToPriorItem();
  258.  
  259. Special list functions are convenient to use in situations where many 
  260. operations are to be performed on the same list.  Just store the list record 
  261. address of your list into the variable called 'TheList' and then use the 
  262. special list functions.
  263.  
  264. Special list functions use two global variables:
  265.  
  266.     1. 'TheList' holds the address of the current list record.
  267.  
  268.     2. 'TheItem' holds the address of the current item record.
  269.  
  270. For example, suppose you make a list of 3 strings like this:
  271.  
  272.     AddressOfList   abcList;
  273.     Byte            aString[] = "a";
  274.     Byte            bString[] = "b";
  275.     Byte            cString[] = "c";
  276.  
  277.     abcList = CreateList();
  278.  
  279.     InsertDataLastInList(abcList, aString);
  280.     InsertDataLastInList(abcList, bString);
  281.     InsertDataLastInList(abcList, cString);
  282.  
  283.                         'abcList'
  284.                           |
  285.                         [LIST]
  286.                           |
  287.                         [ITEM]-->[a]
  288.                           |
  289.                         [ITEM]-->[b]
  290.                           |
  291.                         [ITEM]-->[c]
  292.  
  293. Now suppose you want to capitalize each string in your list, this is how to 
  294. do it using special list functions:
  295.  
  296. 1. To make the list the current list, store the address of the list record 
  297. into the global variable 'TheList':
  298.  
  299.     TheList = abcList;
  300.  
  301. 2. Call 'ToFirstItem()' to make the first item the current item:
  302.  
  303.     ToFirstItem();
  304.         
  305.                          'abcList'
  306.                            |
  307.              'TheList'-->[LIST]
  308.                            |
  309.              'TheItem'-->[ITEM]-->[a]
  310.                            |
  311.                          [ITEM]-->[b]
  312.                            |
  313.                          [ITEM]-->[c]
  314.  
  315. 3. This code operates on the current item and moves to the next one until 
  316. there are no more items:
  317.  
  318.     /* Operate as long as 'TheItem' is non-zero. */
  319.  
  320.     while( TheItem )     
  321.     {
  322.         /* 'TheDataAddress' refers to the data address of  'TheItem'. */ 
  323.         ConvertStringToUpperCase( (AddressOfString) TheDataAddress );
  324.  
  325.  
  326.         /* Move current item to the NEXT item in the list. */
  327.         ToNextItem();
  328.     }
  329.  
  330. Alternatively, you can get the same result by processing the list in reverse 
  331. order like this:
  332.  
  333.     TheList = abcList;
  334.  
  335.     ToLastItem();   /* Sets current item to be the last item in the list. */
  336.  
  337.     while(TheItem)
  338.     {
  339.         ConvertStringToUpperCase( (AddressOfString) TheDataAddress );
  340.  
  341.         /* Move current item to the PRIOR item in the list. */            
  342.         ToPriorItem();
  343.     }
  344.  
  345. For more examples see the general list functions in file 'ListList.c'  which 
  346. are written in terms of the special list functions.
  347.  
  348. Here's a list of the most commonly used variables, macros and procedures 
  349. associated with the special list:
  350.  
  351. VARIABLES
  352.  
  353. TheList............Holds the list record address of the current list.
  354.  
  355. TheItem............Holds the item record address of the current item.
  356.  
  357.  
  358. MACROS: Use the following as if they were global variables:
  359.  
  360. TheFirstItem.......Refers to the first item field of the current list.
  361.  
  362. TheItemCount.......Refers to the item count field of the current list.
  363.  
  364. TheLastItem........Refers to the last item field of the current list.
  365.  
  366. TheListMark........Refers to the list mark field of the current list.
  367.  
  368.  
  369. TheDataAddress.....Refers to the data address field of current item.
  370.  
  371. TheItemMark........Refers to the item mark field of the current item.
  372.  
  373. TheNextItem........Refers to the next item field of the current item.
  374.  
  375. ThePriorItem.......Refers to the prior item field of the current item.
  376.  
  377.  
  378. PROCEDURES
  379.  
  380. PullTheListAndItem()....Pulls the values of the current list and item 
  381.                         from the list stack.
  382.  
  383. PushTheListAndItem()....Push the values of the current list and item 
  384.                         onto the list stack.
  385.  
  386. ToFirstItem()...........Sets the current item to be the first item
  387.                         in the current list.
  388.  
  389. ToLastItem()............Sets the current item to be the last item
  390.                         in the current list.
  391.  
  392. ToNextItem()............Sets the current item to be the item following 
  393.                         the current item.
  394.  
  395. ToPriorItem()...........Sets the current item to be the item preceding
  396.                         the current item.
  397.  
  398. See the file 'ListList.h' for a complete list of all procedures and macros 
  399. in the ListList library.
  400.  
  401.  
  402. THE LIST STACK: A CONVENIENT PLACE TO PRESERVE LIST ADDRESSES.................
  403.  
  404. The above special list example assumes that there are no other pending 
  405. procedures which depend on the values held in 'TheList' and 'TheItem'.  
  406. To use 'TheList' and 'TheItem' without interfering with other procedures 
  407. which may also use these variables, you need to preserve and restore their 
  408. values.  
  409.  
  410. One way to do this is to save them on a special stack designed exclusively 
  411. for this purpose.  Here's a procedure that shows how:
  412.  
  413. Nothing
  414. CapitalizeList(AddressOfList AList)
  415. {
  416.     PushTheListAndItem();  /* Push the current list and item onto the list 
  417.                             * stack.
  418.                             */
  419.     TheList = AList;
  420.     ToFirstItem();
  421.  
  422.     while(TheItem)
  423.     {
  424.         ConvertStringToUpperCase( (AddressOfString) TheDataAddress );
  425.  
  426.         ToNextItem();
  427.     }
  428.  
  429.     PullTheListAndItem(); /* Pull the current list and item from the
  430.                            * list stack.
  431.                            */
  432. }
  433.  
  434. Use 'PushTheListAndItem()' before any special list operations to preserve the 
  435. current values of 'TheList' and 'TheItem' on the list stack.
  436.  
  437. After you have finished using the special list functions, restore the values 
  438. preserved on the list stack using 'PullTheListAndItem()'.
  439.  
  440. SET UP & CLEAN UP: WHAT TO DO FIRST & LAST....................................
  441.  
  442. Before ListList functions can be used the system must be set up for use.  Call 
  443. the following procedure to pre-allocate memory for use as list and item 
  444. records.
  445.  
  446.     SetUpTheListSystem( MaxCountOfLists, MaxCountOfItems );
  447.  
  448. The parameters you give to this procedure set an upper limit on how many 
  449. lists or items can be used at one time.
  450.  
  451. Use the following procedure to deallocate list and item memory:
  452.  
  453.     CleanUpTheListSytem();
  454.  
  455. GETTING STARTED: RUNNING THE TEST PROGRAM.....................................
  456.  
  457. ListList has been fully tested and is free of errors, but you should compile 
  458. and run the test program, 'ListTest.c', to make sure that it works properly 
  459. with your compiler.  Some revision to the data types in file 'DataSize.h' may 
  460. be required for your system.  
  461.  
  462. PACKING LIST:.................................................................
  463.  
  464. There are 9 files in the ListList product:
  465.  
  466. 1. ListList.DOC..ListList 5.0 User's Guide (this file)
  467. 2. Bytes.c.......Byte manipulation procedures
  468. 3. Bytes.h.......Byte library interface file
  469. 4. DataSize.h....Compiler-specific definitions
  470. 5. ListList.c....List manipulation procedures 
  471. 6. ListList.h....List library interface file
  472. 7. ListTest.c....Test and example program
  473. 8. Strings.c.....String manipulation procedures
  474. 9. Strings.h.....String library interface file
  475.  
  476. Shipped in compressed form as 'ListList.ZIP'.
  477.  
  478. FURTHER READING ON LINKED LISTS:..............................................
  479.  
  480. "Algorithms" by Robert Sedgewick, 2nd Ed. p.17
  481.  
  482. "The Art Of Computer Programming, Vol. 1 Fundamental Algorithms" by 
  483. Donald E. Knuth, 2nd Ed. p. 278
  484.  
  485. USAGE TERMS:..................................................................
  486.  
  487. This is commercial, for-profit software.  As the author, my terms are strict 
  488. but easy to meet: you may use my software if you pay me $5 cash.  
  489.  
  490. If you need a list manager then this is a good deal for both of us: you gain 
  491. by saving several weeks of your most precious resource and I gain by earning 
  492. my living. 
  493.  
  494. Use of ListList in software for profit or pleasure is encouraged.  You may 
  495. resell ListList as part of your product without any limitations.  Feel free 
  496. to edit the source to fit your style and add functions of your own.
  497.  
  498. However, there is one usage restriction: use by government or non-profit 
  499. organizations is prohibited.
  500.  
  501. If you want to use ListList, the price is $5 cash with payment due when you 
  502. have used it to save more than $5 worth of your time.  
  503.  
  504. Please mail cash payment to my permanent address: 
  505.  
  506.     LEE MALONE
  507.     1800 MARKET ST. #221
  508.     SAN FRANCISCO, CA  94102
  509.  
  510. If you have more time than money, you can pay me in another way, by helping 
  511. to distribute my product.  Upload an unaltered copy of 'ListList.ZIP' to a 
  512. new BBS or software library and you will have paid me in full.
  513.  
  514. I value your business.  Comments welcome.
  515.  
  516. Sincerely,
  517.  
  518. Lee Malone
  519.  
  520.  
  521. WARRANTY:  I take pride in the quality of my work and stand by it.  I warrant 
  522. this product to be free of errors and will gladly send a full refund and a 
  523. correction if you find an error that I missed.  
  524.  
  525. ==============================================================================
  526.